package com.tingyuge.base.structrue.quene;


/**
 * @Created by xiaodao
 */
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front ,tail;
    private int size;


    /**
     *有意识的浪费一个空间
     * @param capaCity
     */
    public LoopQueue(int capaCity) {
        this.data = (E[])new Object[capaCity+1];
        front = 0;
        tail = 0;
        size=0;
    }

    public LoopQueue(){
        this(5);
    }


    public int getCapacity(){
        return data.length-1;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public E deQueue() {
        if(isEmpty())
            throw new NullPointerException("队列为空");

        E res = data[front];
        data[front] = null;
        front = (front+1) % data.length;
        size--;
        if(size == getCapacity() /4 && getCapacity() / 2!=0){
            resize(getCapacity() /2);
        }

        return res;
    }

    @Override
    public E getFront() {
        if(isEmpty())
            throw  new NullPointerException("队列为空");
        return data[front];

    }

    @Override
    public void enQueue(E e) {
        //下一个tail的值==front
        if((tail+1)%data.length ==front){
            resize(getCapacity() * 2);
        }

        data[tail] =e;
        tail = (tail+1) % data.length;
        size ++;
    }

    private void resize(int capacity) {
        //依然要浪费一个空间
        E[] newData = (E[]) new Object[capacity +1 ];
        //这里循环队列 要把队首元素放在心的空间的起始位置,但是front 可能不在0的位置 可能有偏移
        for (int i = 0; i <size ; i++) {

            newData[i] = data[ ( i + front) % data.length ];

        }

        data = newData;
        front=0;
        tail=size;

    }
    @Override
    public String toString() {
        System.out.println(data.length);
        StringBuilder builder =new StringBuilder();
        builder.append(String.format("Array: size =%d ,capacity = %d\n ", size, getCapacity()));
        builder.append("LoopQueue: ");
        builder.append("front [");
        //最后一个元素 有可能tail 可能比front 还小.
        for (int i = front; i != tail ; i= (i+1) % data.length ) {
            builder.append(data[i]);
            if( (i+1) % data.length !=tail) //不是最后一个元素
                builder.append(", ");

        }
        builder.append("] tail ");
        return builder.toString();
    }


    public static void main(String[] args) {
        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        loopQueue.enQueue(1);
        loopQueue.enQueue(2);
        loopQueue.enQueue(3);
        loopQueue.enQueue(4);
        loopQueue.enQueue(5);
        loopQueue.enQueue(5);

        System.out.println(loopQueue);
        loopQueue.deQueue();
        loopQueue.deQueue();
        loopQueue.deQueue();
        loopQueue.deQueue();
        System.out.println(loopQueue);
        loopQueue.enQueue(60);
        System.out.println(loopQueue);


    }

}
